/* A* algorithm to solve the 8 puzzle. The heuristic value used for a state is
 * the number of elements in the wrong place + number of steps taken to reach
 * the state. At every iteration the top element i.e. the one with minimum
 * heuristic value is popped. */
#include <iostream>
#include <queue>
#include <string.h>
#include <assert.h>

#define N 3

using namespace std;

void swap(int *x, int *y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}


/* View the cells as matrix to print and manipulate. View them as array to compare and copy */
union Cells
{
    int matrix[N][N];
    int linear[N * N];
};

enum direction
{
    UP, DOWN, LEFT, RIGHT
};

class State
{
    private:
        Cells c;
        int hamming;

    public:
        int steps;
        int heuristic;

        State (int steps, int array[]):hamming (0), steps (steps), heuristic (steps) {
            memcpy (c.linear, array, N * N * sizeof (int));
            calc_hamming ();
            heuristic += hamming;
        }

        int calc_hamming (void)
        {
            for (int i = 0; i < N * N; i++)
            {
                if (c.linear[i] && c.linear[i] != i+1)
                {
                    hamming++;
                }
            }
        }

        bool operator == (const State & state)
        {
            return !(memcmp (c.linear, state.c.linear, N * N * sizeof(int)));
        }

        bool operator != (const State & state)
        {
            return memcmp(c.linear, state.c.linear, N * N * sizeof(int));
        }

        int get_0_pos(void)
        {
            for(int i=0; i<N*N; i++)
            {
                if (c.linear[i] == 0)
                {
                    return i;
                }
            }
        }

        State* get_next_state(enum direction d)
        {
            int zero_pos = get_0_pos();
            int zero_i = zero_pos/N;
            int zero_j = zero_pos%N;

            Cells ncells;
            memcpy(ncells.linear, c.linear, N*N*sizeof(int));

            switch(d)
            {
                case UP:
                    /* Can't move up */
                    if (zero_i == 0)
                    {
                        return NULL;
                    }

                    swap(&ncells.matrix[zero_i][zero_j], &ncells.matrix[zero_i - 1][zero_j]);
                    break;

                case DOWN:
                    if (zero_i == N-1)
                    {
                        return NULL;
                    }

                    swap(&ncells.matrix[zero_i][zero_j], &ncells.matrix[zero_i + 1][zero_j]);
                    break;

                case LEFT:
                    if (zero_j == 0)
                    {
                        return NULL;
                    }

                    swap(&ncells.matrix[zero_i][zero_j], &ncells.matrix[zero_i][zero_j - 1]);
                    break;

                case RIGHT:
                    if (zero_j == N-1)
                    {
                        return NULL;
                    }

                    swap(&ncells.matrix[zero_i][zero_j], &ncells.matrix[zero_i][zero_j + 1]);
                    break;

                default:
                    assert(0);

            }

            return new State(steps + 1, ncells.linear);
        }

        void print(void)
        {
            for (int i=0; i < N; i++)
            {
                for (int j=0; j < N; j++)
                {
                    cout.width(4);
                    cout << c.matrix[i][j];
                }
                cout << endl;
            }
            cout << endl;
        }
};


class State_comparison
{
    public:
        bool operator () (const State * lhs, const State * rhs)
        {
            return lhs->heuristic > rhs->heuristic;
        }
};

priority_queue < State *, vector < State * >, State_comparison > state_heap;

int initial[] = { 4, 1, 3, 7, 2, 5, 8, 0, 6};
int final[] = { 1, 2, 3, 4, 5, 6, 7, 8, 0 };

State initial_state (0, initial);
State final_state (0, final);	/* The number does not matter here. We only compare the cells */

int main (void)
{
    state_heap.push (&initial_state);
    State *state = state_heap.top ();

    State prev_state = *state;
    State cur_state = *state_heap.top();

    while (cur_state != final_state)
    {
        cur_state.print();
        state_heap.pop();

        State *new_state;

        new_state = cur_state.get_next_state(UP);
        if (new_state != NULL && (*new_state != prev_state))
        {
            state_heap.push(new_state);
        }

        new_state = cur_state.get_next_state(DOWN);
        if (new_state != NULL && (*new_state != prev_state))
        {
            state_heap.push(new_state);
        }

        new_state = cur_state.get_next_state(LEFT);
        if (new_state != NULL && (*new_state != prev_state))
        {
            state_heap.push(new_state);
        }

        new_state = cur_state.get_next_state(RIGHT);
        if (new_state != NULL && (*new_state != prev_state))
        {
            state_heap.push(new_state);
        }

        prev_state = cur_state;
        cur_state = *state_heap.top();
    }
    cur_state.print();

    return 0;
}
